package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/add-two-numbers/">两数相加(Add Two Numbers)</a>
 * <p>给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。</p>
 * <p>请你将两个数相加，并以相同形式返回一个表示和的链表。</p>
 * <p>你可以假设除了数字 0 之外，这两个数都不会以 0 开头。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：l1 = [2,4,3], l2 = [5,6,4]
 *      输出：[7,0,8]
 *      解释：342 + 465 = 807.
 *
 * 示例 2：
 *      输入：l1 = [0], l2 = [0]
 *      输出：[0]
 *
 * 示例 3：
 *      输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 *      输出：[8,9,9,9,0,0,0,1]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>每个链表中的节点数在范围 [1, 100] 内</li>
 *         <li>0 <= Node.val <= 9</li>
 *         <li>题目数据保证列表表示的数字不含前导零</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/10/12 16:26
 */
public class LC0002AddTwoNumbers_M {
    static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            int sign = 0;
            while (sign != 0 || l1 != null || l2 != null) {
                if (l1 != null) {
                    sign += l1.val;
                    l1 = l1.next;
                }
                if (l2 != null) {
                    sign += l2.val;
                    l2 = l2.next;
                }
                currNode.next = new ListNode(sign % 10);
                currNode = currNode.next;
                sign = sign / 10;
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node;
        ListNode t1ListNode1 = new ListNode(2);
        t1ListNode1.next = new ListNode(4);
        t1ListNode1.next.next = new ListNode(9);
        ListNode t1ListNode2 = new ListNode(5);
        t1ListNode2.next = new ListNode(6);
        t1ListNode2.next.next = new ListNode(4);
        t1ListNode2.next.next.next = new ListNode(9);
        node = solution.addTwoNumbers(t1ListNode1, t1ListNode2);
        while (node != null) {
            System.out.print(node.val + ",");
            node = node.next;
        }
        System.out.println();
        ListNode t2ListNode1 = new ListNode(0);
        ListNode t2ListNode2 = new ListNode(0);
        node = solution.addTwoNumbers(t2ListNode1, t2ListNode2);
        while (node != null) {
            System.out.print(node.val);
            node = node.next;
        }
        System.out.println();
        ListNode t3ListNode1 = new ListNode(9);
        t3ListNode1.next = new ListNode(9);
        t3ListNode1.next.next = new ListNode(9);
        t3ListNode1.next.next.next = new ListNode(9);
        t3ListNode1.next.next.next.next = new ListNode(9);
        t3ListNode1.next.next.next.next.next = new ListNode(9);
        t3ListNode1.next.next.next.next.next.next = new ListNode(9);
        ListNode t3ListNode2 = new ListNode(9);
        t3ListNode2.next = new ListNode(9);
        t3ListNode2.next.next = new ListNode(9);
        t3ListNode2.next.next.next = new ListNode(9);
        node = solution.addTwoNumbers(t3ListNode1, t3ListNode2);
        while (node != null) {
            System.out.print(node.val);
            node = node.next;
        }
    }
}
